class Solution {
public:
    vector<string> ans;
    void dfs(string& s, int n, int m) {
        if (n == 0 && m == 0) {
            ans.push_back(s);
            return;
        }
        if (n) {
            s.push_back('(');
            n -= 1;
            dfs(s, n, m);
            s.pop_back();
            n += 1;
        }
        if (n < m) {
            s.push_back(')');
            m -= 1;
            dfs(s, n, m);
            s.pop_back();
            m += 1;
        }
    }
    vector<string> generateParenthesis(int n) {
        string s;
        dfs(s, n, n);
        return ans;
    }
};